<HTML>
<HEAD>
<title>Falling</title>
</head>
<BODY>

<center>
<h1>CEOI 2000 Day 2 Problem 1</h1>
<h1>Falling</h1>
</center>

<p>
Consider a game based on the device shown in the image below:
<CENTER><img src="image/205.gif"></CENTER>
The device
consists in a set of horizontal platforms of various lengths, placed at 
various heights. The lowest platform is the floor (it is placed at height 
0 and has an infinite length).
<p>
From a given position, a ball is
released in free fall at moment 0. The ball falls at a constant speed of 1 
meter per second. When the ball reaches a platform it starts rolling 
towards one or the other of its edges, at the choice of the player, at the 
same speed of one meter per second. When it reaches the edge of the 
platform, it continues its vertical free fall. The ball is not allowed to 
free fall for more then MAX meters at one time (between two platforms). 

<h2>Task</h2>
Write a program that finds a way to roll the ball
on the platforms so that it reaches the floor as soon as possible without 
breaking.

<h2>Input</h2>
File name: <B>FALL.IN</B> <BR>
<B>Line 1</B>: N X Y MAX 
<LI>Four integers, separated by a space: the number of platforms 
(excluding the floor), the starting position of the ball (horizontal and 
vertical coordinates), and the maximum allowed free fall distance; the 
platforms are numbered from 1 through N.<BR>
<B>Lines 2..<I>N</I>+1</B>:X1<SUB>i</SUB> X2<SUB>i</SUB> H<SUB>i</SUB>
<LI>Three integers, separated by spaces; the <I>i</I>-th platform is 
situated at height H<SUB>i</SUB>, between horizontal coordinates 
X1<SUB>i</SUB> and X2<SUB>i</SUB> inclusive (X1<SUB>i</SUB> &lt; 
X2<SUB>i</SUB>, <I>i</I>=1..N).

<h2>Remarks</h2>
<LI>Ignore the ball diameter and platform thickness. If the ball falls 
exactly on the edge of a platform, it is considered a fall onto that 
platform. 
<LI>No two platforms have points in common. 
<LI>There will always be a solution for the test data. 
<LI>All the dimensions are given in meters.

<h2>Output</h2>
File name: <B>FALL.OUT</B><BR>
<B>Line 1</B>: TIME
<LI>An integer: the time when the ball touches the floor, according to 
your solution. <br>
<B>The rest of the lines, to the end of the file</B>: P T D
<LI>Three integers, separated by spaces. The ball touches the platform P 
at moment T and rolls in direction D (0 for left and 1 for right). 
<LI>The impact with the floor must not appear in these lines. 
<LI>The impacts must be output such that the successive values of T appear 
in increasing order.

<h2>Remark</h2>
If there are several solutions possible, only one is required 

<h2>Limits</h2>
<LI>1 &lt;= N &lt;= 1000 <br>
<LI>-20000 &lt;= X1<SUB>i</SUB>, X2<SUB>i</SUB> &lt;= 20000 ( i=1..N ) 
<LI>0 &lt; H<SUB>i</SUB> &lt; Y &lt;= 20000

<h2>Sample Input</h2>
<pre>
3 8 17 20
0 10 8
0 10 13
4 14 3
</pre>

<h2>Sample Output</h2>
<pre>
23
2 4 1
1 11 1
3 16 1
</PRE>

</BODY></HTML>
